Buses run to Tacna from Lima 20 hours and points south along the coast, including Nazca 12 hours, as well as Arequipa.
To get to Arica, Chile, take a collectivo taxi from the International Terminal, located next to the domestic bus terminal. You will encounter many touts on the way between terminals, but you may wish to wait until inside the terminal to secure transport as prices vary slightly. Although you will no doubt be assured that the collectivo is leaving right away, this is often not the case as they will not leave until full if you are in a group of 4 or more you may wish to try and negotiate your own taxi. The driver will help you through customs and immigration. The journey takes between 1.5 and 2 hours, depending how long border formalities take. The collectivo will drop you at the bus terminal in Arica; you can try and negotiate a ride to your accommodation but this may not be possible.